DungeonGame.java

packagesection19_DynamicProgramming;

publicclassDungeonGame {

publicstaticvoidmain(String[] args) {

int[][] dungeon = { { -2, -3, 3 }, { -5, -10, 1 }, { 10, 30, -5 } };
intcurrRow = 0, currCol = 0;
intendRow = dungeon.length - 1, endCol = dungeon[0].length - 1;

System.out.println(knightMinHealthRecursion(dungeon, currRow, currCol, endRow, endCol));

// top down DP
int[][] storage = newint[endRow + 1][endCol + 1];
System.out.println(knightMinHealthTopDownDP(dungeon, 0, 0, endRow, endCol, storage));

// bottom up DP
System.out.println(knightMinHealthBottomUpDP(dungeon));
 }

publicstaticintknightMinHealthRecursion(int[][] dungeon, intcr, intcc, inter, intec) {

if (cr > er || cc > ec) {
returnInteger.MAX_VALUE;
 }
if (cr == er && cc == ec) {
if (dungeon[cr][cc] <= 0) {
return1 - dungeon[cr][cc];
 }
return1;
 }

intmoveRight = knightMinHealthRecursion(dungeon, cr, cc + 1, er, ec);
intmoveBottom = knightMinHealthRecursion(dungeon, cr + 1, cc, er, ec);

intminPath = Math.min(moveRight, moveBottom);

inthealthAlreadyHave = minPath - dungeon[cr][cc];

intminHealthRequired;

if (healthAlreadyHave > 0) {
minHealthRequired = healthAlreadyHave;
 } else {
minHealthRequired = 1;
 }

returnminHealthRequired;
 }

publicstaticintknightMinHealthTopDownDP(int[][] dungeon, intcr, intcc, inter, intec, int[][] storage) {

if (cr > er || cc > ec) {
returnInteger.MAX_VALUE;
 }
if (cr == er && cc == ec) {
if (dungeon[cr][cc] <= 0) {
return1 - dungeon[cr][cc];
 }
return1;
 }
if (storage[cr][cc] != 0) {
returnstorage[cr][cc];
 }
intmoveRight = knightMinHealthTopDownDP(dungeon, cr, cc + 1, er, ec, storage);
intmoveBottom = knightMinHealthTopDownDP(dungeon, cr + 1, cc, er, ec, storage);

intminPath = Math.min(moveRight, moveBottom);

inthealthAlreadyHave = minPath - dungeon[cr][cc];

intminHealthRequired;

if (healthAlreadyHave > 0) {
minHealthRequired = healthAlreadyHave;
 } else {
minHealthRequired = 1;
 }

storage[cr][cc] = minHealthRequired;

returnminHealthRequired;
 }

publicstaticintknightMinHealthBottomUpDP(int[][] dungeon) {
intn = dungeon.length;
int[][] storage = newint[n + 1][n + 1];

for (introw = n; row >= 0; row--) {

for (intcol = storage[row].length - 1; col >= 0; col--) {

// base cases
if (row == storage.length - 1 || col == storage[row].length - 1) {
storage[row][col] = Integer.MAX_VALUE;

 } elseif (row == storage.length - 2 && col == storage[row].length - 2) {
intval = 1;
if (dungeon[row][col] < 0) {
val = -dungeon[row][col] + 1;
 }
storage[row][col] = val;

 } else {
// logic from top down

intmoveRight = storage[row][col + 1];
intmoveBottom = storage[row + 1][col];

intminPath = Math.min(moveRight, moveBottom);

inthealthAlreadyHave = minPath - dungeon[row][col];

intminHealthRequired;

if (healthAlreadyHave > 0) {
minHealthRequired = healthAlreadyHave;
 } else {
minHealthRequired = 1;
 }

storage[row][col] = minHealthRequired;
 }
 }
 }

returnstorage[0][0];
 }
}